#include "iostream"
#include "vector"
using namespace std;

int check_landform(int sta ,int landform){  //山地为1
    return !(sta&landform);                 //符合条件返回1
}
int check_selfLine(int sta){
    return !((sta&(sta<<2))||(sta&(sta>>2))||(sta&(sta<<1))||(sta&(sta>>1)));//保证同一行出现的炮兵之间相隔两格
}
int check_preLine(int sta1,int sta2){
    //1.两列上的炮兵不在同一列
    //2.炮兵正上方 不能有其他炮兵的侧翼  
    return !((sta1&sta2)||(sta1&(sta2<<2))||(sta1&(sta2<<1))||(sta1&(sta2>>1))||(sta1&(sta2>>2)));
}



int main(){
    int row=5,col=4;
    vector<vector<int> > dp(row,vector<int>(1<<col,0));
    vector<int> landform(row,0);
    landform[0]=2;
    landform[1]=4;
    landform[2]=0;
    landform[3]=2;
    landform[4]=6;
    for(int i=0;i<row;i++){
        for(int j=0;j<(1<<col);j++){
            dp[i][j] =0;
            cout<<dp[i][j]<<"  ";
        }
        cout<<endl;
    }
    cout<<endl;
    for(int rowIdx=0;rowIdx<row;++rowIdx){
        for(int sub=1;sub<(1<<col);sub++){
            if(!check_landform(sub,landform[rowIdx]) || !check_selfLine(sub)){  //不符合条件
                continue;
            }
            
            cout<<rowIdx<<"  "<<sub<<" "<<"|";
            switch (rowIdx){
                case 0:{    //可以部署
                    dp[rowIdx][sub]=__builtin_popcount(sub);
                    break;
                }
                case 1:{    //自身行+前一行
                    for(int pre=0;pre<(1<<col);pre++){
                        { //找到前一行有效部署方案
                            if(check_preLine(sub,pre)){
                                cout<<endl;
                                cout<<"row :"<<row<<"  sub:  "<<sub<<"  pre:"<<pre<<endl;
                                if(dp[rowIdx][sub]==0){
                                    dp[rowIdx][sub] = dp[rowIdx-1][pre]+__builtin_popcount(sub); //点数+1
                                }
                                else{
                                    dp[rowIdx][sub] = max(dp[rowIdx][sub],dp[rowIdx-1][pre]+__builtin_popcount(sub));
                                }
                            }
                        }
                    }
                    break;
                }   
                default:{   //自身行+前一行+前第二行
                    for(int pre1=0;pre1<(1<<col);pre1++){
                        if(!check_preLine(sub,pre1)){
                            continue;
                        }
                        for(int pre2=0;pre2<(1<<col);pre2++){
                            if(check_preLine(sub,pre2)&&check_preLine(pre1,pre2)){  //可以部署了
                                if(dp[rowIdx][sub]==0){
                                    dp[rowIdx][sub] = dp[rowIdx-1][pre1]+dp[rowIdx-2][pre2]+__builtin_popcount(sub); //方案数+1
                                }
                                else{
                                    dp[rowIdx][sub] = max(dp[rowIdx][sub],dp[rowIdx-1][pre1]+dp[rowIdx-2][pre2]+__builtin_popcount(sub));
                                }
                            }
                        }
                    }
                    break;
                }

            }
        }
    }
    cout<<endl;
    for(int i=0;i<row;i++){
        for(int j=0;j<(1<<col);j++){
            cout<<dp[i][j]<<"  ";
        }
        cout<<endl;
    }
    return 0;
}